//
// Created by Administrator on 2021/6/26.
//
//在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用0来表示.
//
//一次移动定义为选择0与一个相邻的数字（上下左右）进行交换.
//
//最终当板board的结果是[[1,2,3],[4,5,0]]谜板被解开。
//
//给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/sliding-puzzle
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    int slidingPuzzle(vector<vector<int>> &board) {
        /**
         * BFS
         * 从起始状态开始,每次都交换0和相邻的数字,并记录下得到的状态
         * 怎么快速记录状态?
         * 用6位长的string记录,0的位置的状态就6种,分别讨论即可
         * 感觉列斯752题
         */
        unordered_set<string> seen;
        string init;
        string target = "123450";
        for (auto &x:board) {
            for (auto &y:x) {
                init += to_string(y);
            }
        }
        // 添加起始状态
        seen.insert(init);
        // 起始状态就是目标状态
        if (seen.count(target)) return 0;
        //bfs队列
        queue<pair<string, int>> q;
        //队列放入初始状态
        q.emplace(init, 0);
        while (!q.empty()) {
            auto[status, level] = q.front();
            q.pop();
            // 默认新添加的状态都是没见过的
            // 从当前状态找到下一个状态
            for (const auto &x : nextStatus(status)) {
                // 找到目标  返回
                if (x == target) return level + 1;
                // 没找到,未见过的状态,入队
                if (seen.find(x) == seen.end()) {
                    q.emplace(x, level + 1);
                    seen.insert(x);
                }
            }
        }
        return -1;
    }

    /**
     * 从当前状态找下一个状态
     * 0的位置有6种，分别讨论
     * @param curStatus
     * @return
     */
    vector<string> nextStatus(string &curStatus) {
        auto stringPos = curStatus.find('0');
        // 还原到矩阵中的坐标
        unsigned int posX = stringPos % 3;
        unsigned int posY = stringPos / 3;
        // 四个方向的动作
        vector<pair<int, int>> movements{{1,  0},
                                         {-1, 0},
                                         {0,  1},
                                         {0,  -1}};
        vector<string> ret;
        for (auto &[movX, movY]:movements) {
            auto nextX = posX + movX;
            auto nextY = posY + movY;
            if (nextX >= 0 and nextX <= 2 and nextY >= 0 and nextY <= 1) {
                // 在字符串中的坐标
                auto nextStringPos = nextY * 3 + nextX;
                swap(curStatus[stringPos], curStatus[nextStringPos]);
                // 添加到答案中
                ret.push_back(curStatus);
                swap(curStatus[stringPos], curStatus[nextStringPos]);
            }
        }
        return ret;
    }
};
class Solution2 {
private:
    vector<vector<int>> neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // 枚举 status 通过一次交换操作得到的状态
        auto get = [&](string& status) -> vector<string> {
            vector<string> ret;
            int x = status.find('0');
            for (int y: neighbors[x]) {
                swap(status[x], status[y]);
                ret.push_back(status);
                swap(status[x], status[y]);
            }
            return ret;
        };

        string initial;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                initial += char(board[i][j] + '0');
            }
        }
        if (initial == "123450") {
            return 0;
        }

        queue<pair<string, int>> q;
        q.emplace(initial, 0);
        unordered_set<string> seen = {initial};

        while (!q.empty()) {
            auto [status, step] = q.front();
            q.pop();
            for (auto&& next_status: get(status)) {
                if (!seen.count(next_status)) {
                    if (next_status == "123450") {
                        return step + 1;
                    }
                    q.emplace(next_status, step + 1);
                    seen.insert(move(next_status));
                }
            }
        }

        return -1;
    }
};

int main() {
    vector<vector<int>> board{{3, 2, 4},
                              {1, 5, 0}};
    Solution sol;
    cout << sol.slidingPuzzle(board) << endl;
    return 0;
}